package Array;//给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
//
// 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。 
//
// 
//
// 示例 1： 
//
// 
//输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
//输出：[[1,5],[6,9]]
// 
//
// 示例 2： 
//
// 
//输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
//输出：[[1,2],[3,10],[12,16]]
//解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。 
//
// 示例 3： 
//
// 
//输入：intervals = [], newInterval = [5,7]
//输出：[[5,7]]
// 
//
// 示例 4： 
//
// 
//输入：intervals = [[1,5]], newInterval = [2,3]
//输出：[[1,5]]
// 
//
// 示例 5： 
//
// 
//输入：intervals = [[1,5]], newInterval = [2,7]
//输出：[[1,7]]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= intervals.length <= 10⁴ 
// intervals[i].length == 2 
// 0 <= intervals[i][0] <= intervals[i][1] <= 10⁵ 
// intervals 根据 intervals[i][0] 按 升序 排列 
// newInterval.length == 2 
// 0 <= newInterval[0] <= newInterval[1] <= 10⁵ 
// 
// Related Topics 数组 👍 493 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class insert {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        //排序好的区间三种情况 [x,y] [i,j]
        //若y<i 则不重合
        //若i <= y && y<j,说明重合了，合并为 x,j
        //y>=j 则重合合并为 x,y

        //新加入的左右边界
        int left = newInterval[0];
        int right = newInterval[1];
        boolean placed = false;  //是否已经放入newInterval
        List<int[]> ansList = new ArrayList<>(); //存结果
        //遍历每一个数组
        for(int[] inter: intervals){
            int li = inter[0];
            int ri = inter[1];
            //当第一次左边界大于新的右边界的时候，说明该添加进去了，因为要有序
            if(li>right){
                //说明不会重叠
                if(!placed){
                    ansList.add(new int[]{left,right});
                    placed = true;
                }
                //添加当前的数组
                ansList.add(inter);
            }else if(ri<left){
                //当前的右边界小于新左边界，也不可能重叠
                ansList.add(inter);
            }else{
                //重叠，合并两个区间并更新，left,right
                // 与插入区间有交集，计算它们的并集
                left = Math.min(left, li);
                right = Math.max(right, ri);
            }
        }
        if(!placed){
            ansList.add(new int[]{left,right});
        }

        int[][] ans = new int[ansList.size()][2];
        for (int i = 0; i < ansList.size(); ++i) {
            ans[i] = ansList.get(i);
        }
        return ans;


    }
}
//leetcode submit region end(Prohibit modification and deletion)
